
//http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
#include<helper.h>
vector<int> a; 
int sw;
const int M=1000000007;
void qsort(int lo,int hi){
    if (lo>=hi) return; printf("qs(%d,%d),sw=%d\n",lo,hi,sw);
    int t,v=a[lo],i=lo,j=hi+1;
    while (1){
        while (a[++i]<v && i<hi) ;
        while (a[--j]>v && j>lo) ;
        if (i>=j) break;
        t=a[i],a[i]=a[j],a[j]=t;sw=(sw+1)%M;
    }
    t=a[lo],a[lo]=a[j],a[j]=t;if(lo!=j) sw=(sw+1)%M;
    qsort(lo,j-1);
    qsort(j+1,hi);
}
int InversePairs(vector<int> data) {
    a=data;
    sw=0;
    qsort(0,a.size()-1);
    return sw;
   
}


int main(){
    int bb1[]={1,5,4,7,2,3,8,6};
    int bb2[]={1,2,3,4,5,6,7,0};
    int bb[]={364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,
    142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,
    80,45,848,38,811,267,575};
    vector<int> b(bb,bb+100);

    printf("%d\n",InversePairs(b));
    prt(b);
    prt(a);
    return 0;
}